package Binary_tree;
// 从树的任意节点出发，到达任意节点，求最多经过的节点数（不能重复经过某个节点）
public class Code05_MaxPathLen {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            value = val;
        }
    }

    public static class Data{
        public int height;
        public int maxPathLen;

        public Data(int h, int m){
            height = h;
            maxPathLen = m;
        }
    }

    public static Data func(Node x){
        if (x == null){
            return null;
        }
        Data leftData = func(x.left);
        Data rightData = func(x.right);

        int height = 1 + Math.max((leftData == null ? 0 : leftData.height),
                (rightData == null ? 0 : rightData.height));
        int maxPathLen = 1 + (leftData == null ? 0 : leftData.height) + (rightData == null ? 0 : rightData.height);
        if (leftData != null){
            maxPathLen = Math.max(maxPathLen, leftData.maxPathLen);
        }
        if (rightData != null){
            maxPathLen = Math.max(maxPathLen, rightData.maxPathLen);
        }
        return new Data(height, maxPathLen);
    }

    public static void main(String[] args) {
        Node head = new Node(4);
        head.left = new Node(1);
        head.left.right = new Node(5);
        head.right = new Node(-7);
        head.right.left = new Node(3);
        System.out.println(func(head).maxPathLen);
    }
}
